// cd25 [动态规划dp]最长递增子序列/最长上升子序列
// https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927
//[LIS(Longest Increasing Subsequence)]
// dp[i] 表示以i结尾的子序列中LIS的长度。然后我用dp[j](0 <= j < i)
// 来表示在i之前的LIS的长度。 然后我们可以看到，只有当a[i] > a[j]
// 的时候，我们需要进行判断，是否将a[i] 加入到dp[j] 当中。
// 为了保证我们每次加入都是得到一个最优的LIS，有两点需要注意：
// 第一，每一次，a[i] 都应当加入最大的那个dp[j].
// 保证局部性质最优，需要找到max(dp[j](0 <= j < i))
// 第二，每一次加入之后，我们都应当更新dp[j] 的值，显然，dp[i] = dp[j] + 1。
// 如果写成递推公式，我们可以得到dp[i]=max(dp[j](0 <= j < i))+(a[i] > a[j] ? 1 :
// 0) 于是我们就能够得到O(n ^ 2) 的动态规划方法的实现： 输入：9 2 1 5 3 6 4 8 9
// 7 输出： 1 3 4 8 9 输入： 5 1 2 8 6 4 输出：1 2 4
// 其最长递增子序列有3个.1,2,8、1,2,6、1,2,4 其中第三个字典序最小，答案1,2,4
//  dp

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution {
 public:
  int lengthOfLIS(vector<int> nums) {
    int n = nums.size();
    if (n == 0) {
      return 0;
    }
    // memo[index]表示在[0…index]的范围内，
    // 选择数字nums[index]可以获得的最长上升子序列的长度。
    vector<int> memo(n, 1);
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          memo[i] = max(memo[i], memo[j] + 1);
        }
      }
    }
    int res = -1;
    for (int i = 0; i < n; i++) {
      res = max(res, memo[i]);
    }
    return res;
  }
};
